#include <gtest/gtest.h>

#include <vector>

#include "algorithm/dp/include/canPartition.h"
#include "algorithm/dp/include/coinChange.h"
#include "algorithm/dp/include/findTargetSumWays.h"
#include "algorithm/dp/include/isMatch.h"
#include "algorithm/dp/include/lengthOfLIS.h"
#include "algorithm/dp/include/lengthOfLongestSubstring.h"
#include "algorithm/dp/include/longestCommonSubsequence.h"
#include "algorithm/dp/include/longestPalindrome.h"
#include "algorithm/dp/include/longestPalindromeSubseq.h"
#include "algorithm/dp/include/maxProfit.h"
#include "algorithm/dp/include/maxValue.h"
#include "algorithm/dp/include/maximalSquare.h"
#include "algorithm/dp/include/minPathSum.h"
#include "algorithm/dp/include/nthUglyNumber.h"
#include "algorithm/dp/include/numTrees.h"
#include "algorithm/dp/include/rob.h"
#include "algorithm/dp/include/uniquePaths.h"
#include "algorithm/dp/include/wordBreak.h"

TEST(TestPriceOfShare, CommonSuits) {
    std::vector<int> a = {7, 1, 5, 3, 6, 4};
    EXPECT_EQ(maxProfit(a), 5);
    a = {7, 6, 4, 3, 1};
    EXPECT_EQ(maxProfit(a), 0);
}

TEST(TestRob, DPSuits) {
    std::vector<int> nums1 = {1, 2, 3, 1};
    std::vector<int> nums2 = {2, 7, 9, 3, 1};
    EXPECT_EQ(robRecursive(nums1), 4);
    EXPECT_EQ(robRecursive(nums2), 12);
    EXPECT_EQ(rob(nums1), 4);
    EXPECT_EQ(rob(nums2), 12);
}

TEST(TestCoin, DPSuits) {
    std::vector<int> nums1 = {1, 2, 5};
    EXPECT_EQ(coinChange(nums1, 1), 1);
    EXPECT_EQ(coinChange(nums1, 2), 1);
    EXPECT_EQ(coinChange(nums1, 3), 2);
    EXPECT_EQ(coinChange(nums1, 4), 2);
    nums1 = {2};
    EXPECT_EQ(coinChange(nums1, 3), -1);
    nums1 = {2, 5, 10, 1};
    EXPECT_EQ(coinChange(nums1, 27), 4);
}

TEST(TestLis, DPSuits) {
    std::vector<int> nums1 = {1, 1, 1, 1, 1, 1};
    EXPECT_EQ(lengthOfLIS(nums1), 1);
    nums1 = {1, 0, 1, 0, 2, 3};
    EXPECT_EQ(lengthOfLIS(nums1), 4);
    nums1 = {10, 9, 2, 5, 3, 7, 101, 18};
    EXPECT_EQ(lengthOfLIS(nums1), 4);
    nums1 = {4, 10, 4, 3, 8, 9};
    EXPECT_EQ(lengthOfLIS(nums1), 3);
}

TEST(TestLongestPaliSubSeq, DPSuits) {
    std::string str = "bbbab";
    EXPECT_EQ(longestPalindromeSubseq(str), 4);
}

TEST(TestUniquePaths, DPSuits) {
    EXPECT_EQ(uniquePaths(3, 7), 28);
    EXPECT_EQ(uniquePaths(3, 2), 3);
}

TEST(TestMaxValue, DPSuits) {
    std::vector<std::vector<int>> values = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
    EXPECT_EQ(minPathSum(values), 7);
}

TEST(TestLongestCommon, DPSuits) {
    std::string s = "abcabcbb";
    EXPECT_EQ(lengthOfLongestSubstring(s), 3);
    s = "arabcacfr";
    EXPECT_EQ(lengthOfLongestSubstring(s), 4);
    s = "";
    EXPECT_EQ(lengthOfLongestSubstring(s), 0);
}

TEST(TestFindTargetSumWays, DPSuits) {
    std::vector<int> nums = {1, 1, 1, 1, 1};
    EXPECT_EQ(findTargetSumWays(nums, 3), 5);

    nums = {2, 1, 1, 2};
    EXPECT_EQ(findTargetSumWays(nums, 0), 4);
    nums = {0, 0, 0, 0, 0, 0, 0, 0, 1};
    EXPECT_EQ(findTargetSumWays(nums, 1), 256);

    nums = {1, 999};
    EXPECT_EQ(findTargetSumWays(nums, 998), 1);

    nums = {1};
    EXPECT_EQ(findTargetSumWays(nums, 2), 0);
}

TEST(TestMaxProfit, DPSuits) {
    std::vector<int> nums = {7, 1, 5, 3, 6, 4};
    EXPECT_EQ(maxProfit(nums), 5);
    EXPECT_EQ(maxProfitDp(nums), 5);
    EXPECT_EQ(maxProfitMultDp(nums), 7);
    EXPECT_EQ(maxProfitMultGreedy(nums), 7);
}

TEST(TestWordBreak, DPSuits) {
    string s = "leetcode";
    vector<string> wordDict = {"leet", "code"};
    EXPECT_TRUE(wordBreak(s, wordDict));
    s = "applepenapple";
    wordDict = {"apple", "pen"};
    EXPECT_TRUE(wordBreak(s, wordDict));
}

TEST(TestLongestPalindrome, DPSuits) {
    string s = "babad";
    EXPECT_EQ(longestPalindrome(s), "bab");
}

TEST(TestNthUglyNumber, DPSuits) { EXPECT_EQ(nthUglyNumber(10), 12); }

TEST(TestMaximalSquare, DPSuits) {
    vector<vector<char>> matrix = {{'1', '0', '1', '0', '0'},
                                   {'1', '0', '1', '1', '1'},
                                   {'1', '1', '1', '1', '1'},
                                   {'1', '0', '0', '1', '0'}};

    EXPECT_EQ(maximalSquare(matrix), 4);
    matrix = {{'1', '1'}};
    EXPECT_EQ(maximalSquare(matrix), 1);
}

TEST(TestIsMatch, DPSuits) {

    EXPECT_FALSE(isMatch("aa", "a"));
    EXPECT_TRUE(isMatch("ab", ".*"));
    //  EXPECT_TRUE(isMatch("aa", "a*"));
}

TEST(TestCanPartition, CommonSuits) {
    vector<int> nums = {1, 5, 11, 5};
    EXPECT_TRUE(canPartition(nums));
    nums = {2, 2, 3, 5};
    EXPECT_FALSE(canPartition(nums));
    nums = {3, 3, 3, 4, 5};
    EXPECT_TRUE(canPartition(nums));
    nums = {1, 5, 10, 6};
    EXPECT_TRUE(canPartition(nums));
}

TEST(TestNumTrees, CommonSuits) {
    vector<int> nums = {1, 5, 11, 5};
    EXPECT_EQ(numTrees(3), 5);
}
